home *** CD-ROM | disk | FTP | other *** search
/ SGI Freeware 1999 August / SGI Freeware 1999 August.iso / dist / samba.idb / usr / samba / src / source / ubiqx / ubi_BinTree.h.z / ubi_BinTree.h
Encoding:
C/C++ Source or Header  |  1998-10-28  |  34.6 KB  |  739 lines
  1. #ifndef ubi_BinTree_H
  2. #define ubi_BinTree_H
  3. /* ========================================================================== **
  4.  *                              ubi_BinTree.h
  5.  *
  6.  *  Copyright (C) 1991-1997 by Christopher R. Hertel
  7.  *
  8.  *  Email:  crh@ubiqx.mn.org
  9.  * -------------------------------------------------------------------------- **
  10.  *
  11.  *  This module implements a simple binary tree.
  12.  *
  13.  * -------------------------------------------------------------------------- **
  14.  *
  15.  *  This library is free software; you can redistribute it and/or
  16.  *  modify it under the terms of the GNU Library General Public
  17.  *  License as published by the Free Software Foundation; either
  18.  *  version 2 of the License, or (at your option) any later version.
  19.  *
  20.  *  This library is distributed in the hope that it will be useful,
  21.  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  22.  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  23.  *  Library General Public License for more details.
  24.  *
  25.  *  You should have received a copy of the GNU Library General Public
  26.  *  License along with this library; if not, write to the Free
  27.  *  Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  28.  *
  29.  * -------------------------------------------------------------------------- **
  30.  *
  31.  * Log: ubi_BinTree.h,v
  32.  * Revision 2.5  1997/12/23 03:59:21  crh
  33.  * In this version, all constants & macros defined in the header file have
  34.  * the ubi_tr prefix.  Also cleaned up anything that gcc complained about
  35.  * when run with '-pedantic -fsyntax-only -Wall'.
  36.  *
  37.  * Revision 2.4  1997/07/26 04:11:14  crh
  38.  * + Just to be annoying I changed ubi_TRUE and ubi_FALSE to ubi_trTRUE
  39.  *   and ubi_trFALSE.
  40.  * + There is now a type ubi_trBool to go with ubi_trTRUE and ubi_trFALSE.
  41.  * + There used to be something called "ubi_TypeDefs.h".  I got rid of it.
  42.  * + Added function ubi_btLeafNode().
  43.  *
  44.  * Revision 2.3  1997/06/03 05:15:27  crh
  45.  * Changed TRUE and FALSE to ubi_TRUE and ubi_FALSE to avoid conflicts.
  46.  * Also changed the interface to function InitTree().  See the comments
  47.  * for this function for more information.
  48.  *
  49.  * Revision 2.2  1995/10/03 22:00:40  CRH
  50.  * Ubisized!
  51.  * 
  52.  * Revision 2.1  95/03/09  23:43:46  CRH
  53.  * Added the ModuleID static string and function.  These modules are now
  54.  * self-identifying.
  55.  * 
  56.  * Revision 2.0  95/02/27  22:00:33  CRH
  57.  * Revision 2.0 of this program includes the following changes:
  58.  *
  59.  *     1)  A fix to a major typo in the RepaceNode() function.
  60.  *     2)  The addition of the static function Border().
  61.  *     3)  The addition of the public functions FirstOf() and LastOf(), which
  62.  *         use Border(). These functions are used with trees that allow
  63.  *         duplicate keys.
  64.  *     4)  A complete rewrite of the Locate() function.  Locate() now accepts
  65.  *         a "comparison" operator.
  66.  *     5)  Overall enhancements to both code and comments.
  67.  *
  68.  * I decided to give this a new major rev number because the interface has
  69.  * changed.  In particular, there are two new functions, and changes to the
  70.  * Locate() function.
  71.  *
  72.  * Revision 1.0  93/10/15  22:55:04  CRH
  73.  * With this revision, I have added a set of #define's that provide a single,
  74.  * standard API to all existing tree modules.  Until now, each of the three
  75.  * existing modules had a different function and typedef prefix, as follows:
  76.  *
  77.  *       Module        Prefix
  78.  *     ubi_BinTree     ubi_bt
  79.  *     ubi_AVLtree     ubi_avl
  80.  *     ubi_SplayTree   ubi_spt
  81.  *
  82.  * To further complicate matters, only those portions of the base module
  83.  * (ubi_BinTree) that were superceeded in the new module had the new names.
  84.  * For example, if you were using ubi_AVLtree, the AVL node structure was
  85.  * named "ubi_avlNode", but the root structure was still "ubi_btRoot".  Using
  86.  * SplayTree, the locate function was called "ubi_sptLocate", but the next
  87.  * and previous functions remained "ubi_btNext" and "ubi_btPrev".
  88.  *
  89.  * This was not too terrible if you were familiar with the modules and knew
  90.  * exactly which tree model you wanted to use.  If you wanted to be able to
  91.  * change modules (for speed comparisons, etc), things could get messy very
  92.  * quickly.
  93.  *
  94.  * So, I have added a set of defined names that get redefined in any of the
  95.  * descendant modules.  To use this standardized interface in your code,
  96.  * simply replace all occurances of "ubi_bt", "ubi_avl", and "ubi_spt" with
  97.  * "ubi_tr".  The "ubi_tr" names will resolve to the correct function or
  98.  * datatype names for the module that you are using.  Just remember to
  99.  * include the header for that module in your program file.  Because these
  100.  * names are handled by the preprocessor, there is no added run-time
  101.  * overhead.
  102.  *
  103.  * Note that the original names do still exist, and can be used if you wish
  104.  * to write code directly to a specific module.  This should probably only be
  105.  * done if you are planning to implement a new descendant type, such as
  106.  * red/black trees.  CRH
  107.  *
  108.  *  V0.0 - June, 1991   -  Written by Christopher R. Hertel (CRH).
  109.  *
  110.  * ========================================================================== **
  111.  */
  112.  
  113. /* -------------------------------------------------------------------------- **
  114.  * Macros and constants.
  115.  *
  116.  *  General purpose:
  117.  *    ubi_trTRUE  - Boolean TRUE.
  118.  *    ubi_trFALSE - Boolean FALSE.
  119.  *
  120.  *  Flags used in the tree header:
  121.  *    ubi_trOVERWRITE   - This flag indicates that an existing node may be
  122.  *                        overwritten by a new node with a matching key.
  123.  *    ubi_trDUPKEY      - This flag indicates that the tree allows duplicate
  124.  *                        keys.  If the tree does allow duplicates, the
  125.  *                        overwrite flag is ignored.
  126.  *
  127.  *  Node link array index constants:  (Each node has an array of three
  128.  *  pointers.  One to the left, one to the right, and one back to the
  129.  *  parent.)
  130.  *    ubi_trLEFT    - Left child pointer.
  131.  *    ubi_trPARENT  - Parent pointer.
  132.  *    ubi_trRIGHT   - Right child pointer.
  133.  *    ubi_trEQUAL   - Synonym for PARENT.
  134.  *
  135.  *  ubi_trCompOps:  These values are used in the ubi_trLocate() function.
  136.  *    ubi_trLT  - request the first instance of the greatest key less than
  137.  *                the search key.
  138.  *    ubi_trLE  - request the first instance of the greatest key that is less
  139.  *                than or equal to the search key.
  140.  *    ubi_trEQ  - request the first instance of key that is equal to the
  141.  *                search key.
  142.  *    ubi_trGE  - request the first instance of a key that is greater than
  143.  *                or equal to the search key.
  144.  *    ubi_trGT  - request the first instance of the first key that is greater
  145.  *                than the search key.
  146.  * -------------------------------------------------------------------------- **
  147.  */
  148.  
  149. #define ubi_trTRUE  0xFF
  150. #define ubi_trFALSE 0x00
  151.  
  152. #define ubi_trOVERWRITE 0x01        /* Turn on allow overwrite      */
  153. #define ubi_trDUPKEY    0x02        /* Turn on allow duplicate keys */
  154.  
  155. /* Pointer array index constants... */
  156. #define ubi_trLEFT   0x00
  157. #define ubi_trPARENT 0x01
  158. #define ubi_trRIGHT  0x02
  159. #define ubi_trEQUAL  ubi_trPARENT
  160.  
  161. typedef enum {
  162.   ubi_trLT = 1,
  163.   ubi_trLE,
  164.   ubi_trEQ,
  165.   ubi_trGE,
  166.   ubi_trGT
  167.   } ubi_trCompOps;
  168.  
  169. /* -------------------------------------------------------------------------- **
  170.  * These three macros allow simple manipulation of pointer index values (LEFT,
  171.  * RIGHT, and PARENT).
  172.  *
  173.  *    Normalize() -  converts {LEFT, PARENT, RIGHT} into {-1, 0 ,1}.  C
  174.  *                   uses {negative, zero, positive} values to indicate
  175.  *                   {less than, equal to, greater than}.
  176.  *    AbNormal()  -  converts {negative, zero, positive} to {LEFT, PARENT,
  177.  *                   RIGHT} (opposite of Normalize()).  Note: C comparison
  178.  *                   functions, such as strcmp(), return {negative, zero,
  179.  *                   positive} values, which are not necessarily {-1, 0,
  180.  *                   1}.  This macro uses the the ubi_btSgn() function to
  181.  *                   compensate.
  182.  *    RevWay()    -  converts LEFT to RIGHT and RIGHT to LEFT.  PARENT (EQUAL)
  183.  *                   is left as is.
  184.  * -------------------------------------------------------------------------- **
  185.  */
  186. #define ubi_trNormalize(W) ((char)( (W) - ubi_trEQUAL ))
  187. #define ubi_trAbNormal(W)  ((char)( ((char)ubi_btSgn( W )) + ubi_trEQUAL ))
  188. #define ubi_trRevWay(W)    ((char)( ubi_trEQUAL - ((W) - ubi_trEQUAL) ))
  189.  
  190. /* -------------------------------------------------------------------------- **
  191.  * These macros allow us to quickly read the values of the OVERWRITE and
  192.  * DUPlicate KEY bits of the tree root flags field.
  193.  * -------------------------------------------------------------------------- **
  194.  */
  195. #define ubi_trDups_OK(A) \
  196.         ((ubi_trDUPKEY & ((A)->flags))?(ubi_trTRUE):(ubi_trFALSE))
  197. #define ubi_trOvwt_OK(A) \
  198.         ((ubi_trOVERWRITE & ((A)->flags))?(ubi_trTRUE):(ubi_trFALSE))
  199.  
  200. /* -------------------------------------------------------------------------- **
  201.  * Typedefs...
  202.  * 
  203.  * ubi_trBool   - Your typcial true or false...
  204.  *
  205.  * Item Pointer:  The ubi_btItemPtr is a generic pointer. It is used to
  206.  *                indicate a key that is being searched for within the tree.
  207.  *                Searching occurs whenever the ubi_trFind(), ubi_trLocate(),
  208.  *                or ubi_trInsert() functions are called.
  209.  * -------------------------------------------------------------------------- **
  210.  */
  211.  
  212. typedef unsigned char ubi_trBool;
  213.  
  214. typedef void *ubi_btItemPtr;              /* A pointer to data within a node. */
  215.  
  216. /*  ------------------------------------------------------------------------- **
  217.  *  Binary Tree Node Structure:  This structure defines the basic elements of
  218.  *       the tree nodes.  In general you *SHOULD NOT PLAY WITH THESE FIELDS*!
  219.  *       But, of course, I have to put the structure into this header so that
  220.  *       you can use it as a building block.
  221.  *
  222.  *  The fields are as follows:
  223.  *    Link     -  an array of pointers.  These pointers are manipulated by
  224.  *                the BT routines.  The pointers indicate the left and right
  225.  *                child nodes and the parent node.  By keeping track of the
  226.  *                parent pointer, we avoid the need for recursive routines or
  227.  *                hand-tooled stacks to keep track of our path back to the
  228.  *                root.  The use of these pointers is subject to change without
  229.  *                notice.
  230.  *    gender   -  a one-byte field indicating whether the node is the RIGHT or
  231.  *                LEFT child of its parent.  If the node is the root of the
  232.  *                tree, gender will be PARENT.
  233.  *  ------------------------------------------------------------------------- **
  234.  */
  235. typedef struct ubi_btNodeStruct {
  236.   struct ubi_btNodeStruct *Link[ 3 ];
  237.   char                     gender;
  238.   } ubi_btNode;
  239.  
  240. typedef ubi_btNode *ubi_btNodePtr;     /* Pointer to an ubi_btNode structure. */
  241.  
  242. /*  ------------------------------------------------------------------------- **
  243.  * The next three typedefs define standard function types used by the binary
  244.  * tree management routines.  In particular:
  245.  *
  246.  *    ubi_btCompFunc    is a pointer to a comparison function.  Comparison
  247.  *                      functions are passed an ubi_btItemPtr and an
  248.  *                      ubi_btNodePtr.  They return a value that is (<0), 0,
  249.  *                      or (>0) to indicate that the Item is (respectively)
  250.  *                      "less than", "equal to", or "greater than" the Item
  251.  *                      contained within the node.  (See ubi_btInitTree()).
  252.  *    ubi_btActionRtn   is a pointer to a function that may be called for each
  253.  *                      node visited when performing a tree traversal (see
  254.  *                      ubi_btTraverse()).  The function will be passed two
  255.  *                      parameters: the first is a pointer to a node in the
  256.  *                      tree, the second is a generic pointer that may point to
  257.  *                      anything that you like.
  258.  *    ubi_btKillNodeRtn is a pointer to a function that will deallocate the
  259.  *                      memory used by a node (see ubi_btKillTree()).  Since
  260.  *                      memory management is left up to you, deallocation may
  261.  *                      mean anything that you want it to mean.  Just remember
  262.  *                      that the tree *will* be destroyed and that none of the
  263.  *                      node pointers will be valid any more.
  264.  *  ------------------------------------------------------------------------- **
  265.  */
  266.  
  267. typedef  int (*ubi_btCompFunc)( ubi_btItemPtr, ubi_btNodePtr );
  268.  
  269. typedef void (*ubi_btActionRtn)( ubi_btNodePtr, void * );
  270.  
  271. typedef void (*ubi_btKillNodeRtn)( ubi_btNodePtr );
  272.  
  273. /* -------------------------------------------------------------------------- **
  274.  * Tree Root Structure: This structure gives us a convenient handle for
  275.  *                      accessing whole AVL trees.  The fields are:
  276.  *    root  -  A pointer to the root node of the AVL tree.
  277.  *    count -  A count of the number of nodes stored in the tree.
  278.  *    cmp   -  A pointer to the comparison routine to be used when building or
  279.  *             searching the tree.
  280.  *    flags -  A set of bit flags.  Two flags are currently defined:
  281.  *
  282.  *       ubi_trOVERWRITE -  If set, this flag indicates that a new node should
  283.  *         (bit 0x01)       overwrite an old node if the two have identical
  284.  *                          keys (ie., the keys are equal).
  285.  *       ubi_trDUPKEY    -  If set, this flag indicates that the tree is
  286.  *         (bit 0x02)       allowed to contain nodes with duplicate keys.
  287.  *
  288.  *       NOTE: ubi_trInsert() tests ubi_trDUPKEY before ubi_trOVERWRITE.
  289.  *
  290.  * All of these values are set when you initialize the root structure by
  291.  * calling ubi_trInitTree().
  292.  * -------------------------------------------------------------------------- **
  293.  */
  294.  
  295. typedef struct {
  296.   ubi_btNodePtr  root;     /* A pointer to the root node of the tree       */
  297.   unsigned long  count;    /* A count of the number of nodes in the tree   */
  298.   ubi_btCompFunc cmp;      /* A pointer to the tree's comparison function  */
  299.   unsigned char  flags;    /* Overwrite Y|N, Duplicate keys Y|N...         */
  300.   } ubi_btRoot;
  301.  
  302. typedef ubi_btRoot *ubi_btRootPtr;  /* Pointer to an ubi_btRoot structure. */
  303.  
  304.  
  305. /* -------------------------------------------------------------------------- **
  306.  * Function Prototypes.
  307.  */
  308.  
  309. long ubi_btSgn( long x );
  310.   /* ------------------------------------------------------------------------ **
  311.    * Return the sign of x; {negative,zero,positive} ==> {-1, 0, 1}.
  312.    *
  313.    *  Input:  x - a signed long integer value.
  314.    *
  315.    *  Output: the "sign" of x, represented as follows:
  316.    *            -1 == negative
  317.    *             0 == zero (no sign)
  318.    *             1 == positive
  319.    *
  320.    * Note: This utility is provided in order to facilitate the conversion
  321.    *       of C comparison function return values into BinTree direction
  322.    *       values: {LEFT, PARENT, EQUAL}.  It is INCORPORATED into the
  323.    *       AbNormal() conversion macro!
  324.    *
  325.    * ------------------------------------------------------------------------ **
  326.    */
  327.  
  328. ubi_btNodePtr ubi_btInitNode( ubi_btNodePtr NodePtr );
  329.   /* ------------------------------------------------------------------------ **
  330.    * Initialize a tree node.
  331.    *
  332.    *  Input:   a pointer to a ubi_btNode structure to be initialized.
  333.    *  Output:  a pointer to the initialized ubi_btNode structure (ie. the
  334.    *           same as the input pointer).
  335.    * ------------------------------------------------------------------------ **
  336.    */
  337.  
  338. ubi_btRootPtr  ubi_btInitTree( ubi_btRootPtr   RootPtr,
  339.                                ubi_btCompFunc  CompFunc,
  340.                                unsigned char   Flags );
  341.   /* ------------------------------------------------------------------------ **
  342.    * Initialize the fields of a Tree Root header structure.
  343.    *  
  344.    *  Input:   RootPtr   - a pointer to an ubi_btRoot structure to be
  345.    *                       initialized.   
  346.    *           CompFunc  - a pointer to a comparison function that will be used
  347.    *                       whenever nodes in the tree must be compared against
  348.    *                       outside values.
  349.    *           Flags     - One bytes worth of flags.  Flags include
  350.    *                       ubi_trOVERWRITE and ubi_trDUPKEY.  See the header
  351.    *                       file for more info.
  352.    *
  353.    *  Output:  a pointer to the initialized ubi_btRoot structure (ie. the
  354.    *           same value as RootPtr).
  355.    * 
  356.    *  Note:    The interface to this function has changed from that of 
  357.    *           previous versions.  The <Flags> parameter replaces two      
  358.    *           boolean parameters that had the same basic effect.
  359.    * ------------------------------------------------------------------------ **
  360.    */
  361.  
  362. ubi_trBool ubi_btInsert( ubi_btRootPtr  RootPtr,
  363.                          ubi_btNodePtr  NewNode,
  364.                          ubi_btItemPtr  ItemPtr,
  365.                          ubi_btNodePtr *OldNode );
  366.   /* ------------------------------------------------------------------------ **
  367.    * This function uses a non-recursive algorithm to add a new element to the
  368.    * tree.
  369.    *
  370.    *  Input:   RootPtr  -  a pointer to the ubi_btRoot structure that indicates
  371.    *                       the root of the tree to which NewNode is to be added.
  372.    *           NewNode  -  a pointer to an ubi_btNode structure that is NOT
  373.    *                       part of any tree.
  374.    *           ItemPtr  -  A pointer to the sort key that is stored within
  375.    *                       *NewNode.  ItemPtr MUST point to information stored
  376.    *                       in *NewNode or an EXACT DUPLICATE.  The key data
  377.    *                       indicated by ItemPtr is used to place the new node
  378.    *                       into the tree.
  379.    *           OldNode  -  a pointer to an ubi_btNodePtr.  When searching
  380.    *                       the tree, a duplicate node may be found.  If
  381.    *                       duplicates are allowed, then the new node will
  382.    *                       be simply placed into the tree.  If duplicates
  383.    *                       are not allowed, however, then one of two things
  384.    *                       may happen.
  385.    *                       1) if overwritting *is not* allowed, this
  386.    *                          function will return FALSE (indicating that
  387.    *                          the new node could not be inserted), and
  388.    *                          *OldNode will point to the duplicate that is
  389.    *                          still in the tree.
  390.    *                       2) if overwritting *is* allowed, then this
  391.    *                          function will swap **OldNode for *NewNode.
  392.    *                          In this case, *OldNode will point to the node
  393.    *                          that was removed (thus allowing you to free
  394.    *                          the node).
  395.    *                          **  If you are using overwrite mode, ALWAYS  **
  396.    *                          ** check the return value of this parameter! **
  397.    *                 Note: You may pass NULL in this parameter, the
  398.    *                       function knows how to cope.  If you do this,
  399.    *                       however, there will be no way to return a
  400.    *                       pointer to an old (ie. replaced) node (which is
  401.    *                       a problem if you are using overwrite mode).
  402.    *
  403.    *  Output:  a boolean value indicating success or failure.  The function
  404.    *           will return FALSE if the node could not be added to the tree.
  405.    *           Such failure will only occur if duplicates are not allowed,
  406.    *           nodes cannot be overwritten, AND a duplicate key was found
  407.    *           within the tree.
  408.    * ------------------------------------------------------------------------ **
  409.    */
  410.  
  411. ubi_btNodePtr ubi_btRemove( ubi_btRootPtr RootPtr,
  412.                             ubi_btNodePtr DeadNode );
  413.   /* ------------------------------------------------------------------------ **
  414.    * This function removes the indicated node from the tree.
  415.    *
  416.    *  Input:   RootPtr  -  A pointer to the header of the tree that contains
  417.    *                       the node to be removed.
  418.    *           DeadNode -  A pointer to the node that will be removed.
  419.    *
  420.    *  Output:  This function returns a pointer to the node that was removed
  421.    *           from the tree (ie. the same as DeadNode).
  422.    *
  423.    *  Note:    The node MUST be in the tree indicated by RootPtr.  If not,
  424.    *           strange and evil things will happen to your trees.
  425.    * ------------------------------------------------------------------------ **
  426.    */
  427.  
  428. ubi_btNodePtr ubi_btLocate( ubi_btRootPtr RootPtr,
  429.                             ubi_btItemPtr FindMe,
  430.                             ubi_trCompOps CompOp );
  431.   /* ------------------------------------------------------------------------ **
  432.    * The purpose of ubi_btLocate() is to find a node or set of nodes given
  433.    * a target value and a "comparison operator".  The Locate() function is
  434.    * more flexible and (in the case of trees that may contain dupicate keys)
  435.    * more precise than the ubi_btFind() function.  The latter is faster,
  436.    * but it only searches for exact matches and, if the tree contains
  437.    * duplicates, Find() may return a pointer to any one of the duplicate-
  438.    * keyed records.
  439.    *
  440.    *  Input:
  441.    *     RootPtr  -  A pointer to the header of the tree to be searched.
  442.    *     FindMe   -  An ubi_btItemPtr that indicates the key for which to
  443.    *                 search.
  444.    *     CompOp   -  One of the following:
  445.    *                    CompOp     Return a pointer to the node with
  446.    *                    ------     ---------------------------------
  447.    *                   ubi_trLT - the last key value that is less
  448.    *                              than FindMe.
  449.    *                   ubi_trLE - the first key matching FindMe, or
  450.    *                              the last key that is less than
  451.    *                              FindMe.
  452.    *                   ubi_trEQ - the first key matching FindMe.
  453.    *                   ubi_trGE - the first key matching FindMe, or the
  454.    *                              first key greater than FindMe.
  455.    *                   ubi_trGT - the first key greater than FindMe.
  456.    *  Output:
  457.    *     A pointer to the node matching the criteria listed above under
  458.    *     CompOp, or NULL if no node matched the criteria.
  459.    *
  460.    *  Notes:
  461.    *     In the case of trees with duplicate keys, Locate() will behave as
  462.    *     follows:
  463.    *
  464.    *     Find:  3                       Find: 3
  465.    *     Keys:  1 2 2 2 3 3 3 3 3 4 4   Keys: 1 1 2 2 2 4 4 5 5 5 6
  466.    *                  ^ ^         ^                   ^ ^
  467.    *                 LT EQ        GT                 LE GE
  468.    *
  469.    *     That is, when returning a pointer to a node with a key that is LESS
  470.    *     THAN the target key (FindMe), Locate() will return a pointer to the
  471.    *     LAST matching node.
  472.    *     When returning a pointer to a node with a key that is GREATER
  473.    *     THAN the target key (FindMe), Locate() will return a pointer to the
  474.    *     FIRST matching node.
  475.    *
  476.    *  See Also: ubi_btFind(), ubi_btFirstOf(), ubi_btLastOf().
  477.    * ------------------------------------------------------------------------ **
  478.    */
  479.  
  480. ubi_btNodePtr ubi_btFind( ubi_btRootPtr RootPtr,
  481.                           ubi_btItemPtr FindMe );
  482.   /* ------------------------------------------------------------------------ **
  483.    * This function performs a non-recursive search of a tree for any node
  484.    * matching a specific key.
  485.    *
  486.    *  Input:
  487.    *     RootPtr  -  a pointer to the header of the tree to be searched.
  488.    *     FindMe   -  a pointer to the key value for which to search.
  489.    *
  490.    *  Output:
  491.    *     A pointer to a node with a key that matches the key indicated by
  492.    *     FindMe, or NULL if no such node was found.
  493.    *
  494.    *  Note:   In a tree that allows duplicates, the pointer returned *might
  495.    *          not* point to the (sequentially) first occurance of the
  496.    *          desired key.  In such a tree, it may be more useful to use
  497.    *          ubi_btLocate().
  498.    * ------------------------------------------------------------------------ **
  499.    */
  500.  
  501. ubi_btNodePtr ubi_btNext( ubi_btNodePtr P );
  502.   /* ------------------------------------------------------------------------ **
  503.    * Given the node indicated by P, find the (sorted order) Next node in the
  504.    * tree.
  505.    *  Input:   P  -  a pointer to a node that exists in a binary tree.
  506.    *  Output:  A pointer to the "next" node in the tree, or NULL if P pointed
  507.    *           to the "last" node in the tree or was NULL.
  508.    * ------------------------------------------------------------------------ **
  509.    */
  510.  
  511. ubi_btNodePtr ubi_btPrev( ubi_btNodePtr P );
  512.   /* ------------------------------------------------------------------------ **
  513.    * Given the node indicated by P, find the (sorted order) Previous node in
  514.    * the tree.
  515.    *  Input:   P  -  a pointer to a node that exists in a binary tree.
  516.    *  Output:  A pointer to the "previous" node in the tree, or NULL if P
  517.    *           pointed to the "first" node in the tree or was NULL.
  518.    * ------------------------------------------------------------------------ **
  519.    */
  520.  
  521. ubi_btNodePtr ubi_btFirst( ubi_btNodePtr P );
  522.   /* ------------------------------------------------------------------------ **
  523.    * Given the node indicated by P, find the (sorted order) First node in the
  524.    * subtree of which *P is the root.
  525.    *  Input:   P  -  a pointer to a node that exists in a binary tree.
  526.    *  Output:  A pointer to the "first" node in a subtree that has *P as its
  527.    *           root.  This function will return NULL only if P is NULL.
  528.    *  Note:    In general, you will be passing in the value of the root field
  529.    *           of an ubi_btRoot structure.
  530.    * ------------------------------------------------------------------------ **
  531.    */
  532.  
  533. ubi_btNodePtr ubi_btLast( ubi_btNodePtr P );
  534.   /* ------------------------------------------------------------------------ **
  535.    * Given the node indicated by P, find the (sorted order) Last node in the
  536.    * subtree of which *P is the root.
  537.    *  Input:   P  -  a pointer to a node that exists in a binary tree.
  538.    *  Output:  A pointer to the "last" node in a subtree that has *P as its
  539.    *           root.  This function will return NULL only if P is NULL.
  540.    *  Note:    In general, you will be passing in the value of the root field
  541.    *           of an ubi_btRoot structure.
  542.    * ------------------------------------------------------------------------ **
  543.    */
  544.  
  545. ubi_btNodePtr ubi_btFirstOf( ubi_btRootPtr RootPtr,
  546.                              ubi_btItemPtr MatchMe,
  547.                              ubi_btNodePtr p );
  548.   /* ------------------------------------------------------------------------ **
  549.    * Given a tree that a allows duplicate keys, and a pointer to a node in
  550.    * the tree, this function will return a pointer to the first (traversal
  551.    * order) node with the same key value.
  552.    *
  553.    *  Input:  RootPtr - A pointer to the root of the tree.
  554.    *          MatchMe - A pointer to the key value.  This should probably
  555.    *                    point to the key within node *p.
  556.    *          p       - A pointer to a node in the tree.
  557.    *  Output: A pointer to the first node in the set of nodes with keys
  558.    *          matching <FindMe>.
  559.    *  Notes:  Node *p MUST be in the set of nodes with keys matching
  560.    *          <FindMe>.  If not, this function will return NULL.
  561.    * ------------------------------------------------------------------------ **
  562.    */
  563.  
  564. ubi_btNodePtr ubi_btLastOf( ubi_btRootPtr RootPtr,
  565.                             ubi_btItemPtr MatchMe,
  566.                             ubi_btNodePtr p );
  567.   /* ------------------------------------------------------------------------ **
  568.    * Given a tree that a allows duplicate keys, and a pointer to a node in
  569.    * the tree, this function will return a pointer to the last (traversal
  570.    * order) node with the same key value.
  571.    *
  572.    *  Input:  RootPtr - A pointer to the root of the tree.
  573.    *          MatchMe - A pointer to the key value.  This should probably
  574.    *                    point to the key within node *p.
  575.    *          p       - A pointer to a node in the tree.
  576.    *  Output: A pointer to the last node in the set of nodes with keys
  577.    *          matching <FindMe>.
  578.    *  Notes:  Node *p MUST be in the set of nodes with keys matching
  579.    *          <FindMe>.  If not, this function will return NULL.
  580.    * ------------------------------------------------------------------------ **
  581.    */
  582.  
  583. ubi_trBool ubi_btTraverse( ubi_btRootPtr   RootPtr,
  584.                            ubi_btActionRtn EachNode,
  585.                            void           *UserData );
  586.   /* ------------------------------------------------------------------------ **
  587.    * Traverse a tree in sorted order (non-recursively).  At each node, call
  588.    * (*EachNode)(), passing a pointer to the current node, and UserData as the
  589.    * second parameter.
  590.    *  Input:   RootPtr  -  a pointer to an ubi_btRoot structure that indicates
  591.    *                       the tree to be traversed.
  592.    *           EachNode -  a pointer to a function to be called at each node
  593.    *                       as the node is visited.
  594.    *           UserData -  a generic pointer that may point to anything that
  595.    *                       you choose.
  596.    *  Output:  A boolean value.  FALSE if the tree is empty, otherwise TRUE.
  597.    * ------------------------------------------------------------------------ **
  598.    */
  599.  
  600. ubi_trBool ubi_btKillTree( ubi_btRootPtr     RootPtr,
  601.                            ubi_btKillNodeRtn FreeNode );
  602.   /* ------------------------------------------------------------------------ **
  603.    * Delete an entire tree (non-recursively) and reinitialize the ubi_btRoot
  604.    * structure.  Note that this function will return FALSE if either parameter
  605.    * is NULL.
  606.    *
  607.    *  Input:   RootPtr  -  a pointer to an ubi_btRoot structure that indicates
  608.    *                       the root of the tree to delete.
  609.    *           FreeNode -  a function that will be called for each node in the
  610.    *                       tree to deallocate the memory used by the node.
  611.    *
  612.    *  Output:  A boolean value.  FALSE if either input parameter was NULL, else
  613.    *           TRUE.
  614.    *
  615.    * ------------------------------------------------------------------------ **
  616.    */
  617.  
  618. ubi_btNodePtr ubi_btLeafNode( ubi_btNodePtr leader );
  619.   /* ------------------------------------------------------------------------ **
  620.    * Returns a pointer to a leaf node.
  621.    *
  622.    *  Input:  leader  - Pointer to a node at which to start the descent.
  623.    *
  624.    *  Output: A pointer to a leaf node selected in a somewhat arbitrary
  625.    *          manner.
  626.    *
  627.    *  Notes:  I wrote this function because I was using splay trees as a
  628.    *          database cache.  The cache had a maximum size on it, and I
  629.    *          needed a way of choosing a node to sacrifice if the cache
  630.    *          became full.  In a splay tree, less recently accessed nodes
  631.    *          tend toward the bottom of the tree, meaning that leaf nodes
  632.    *          are good candidates for removal.  (I really can't think of
  633.    *          any other reason to use this function.)
  634.    *        + In a simple binary tree or an AVL tree, the most recently
  635.    *          added nodes tend to be nearer the bottom, making this a *bad*
  636.    *          way to choose which node to remove from the cache.
  637.    *        + Randomizing the traversal order is probably a good idea.  You
  638.    *          can improve the randomization of leaf node selection by passing
  639.    *          in pointers to nodes other than the root node each time.  A
  640.    *          pointer to any node in the tree will do.  Of course, if you
  641.    *          pass a pointer to a leaf node you'll get the same thing back.
  642.    *
  643.    * ------------------------------------------------------------------------ **
  644.    */
  645.  
  646.  
  647. int ubi_btModuleID( int size, char *list[] );
  648.   /* ------------------------------------------------------------------------ **
  649.    * Returns a set of strings that identify the module.
  650.    *
  651.    *  Input:  size  - The number of elements in the array <list>.
  652.    *          list  - An array of pointers of type (char *).  This array
  653.    *                  should, initially, be empty.  This function will fill
  654.    *                  in the array with pointers to strings.
  655.    *  Output: The number of elements of <list> that were used.  If this value
  656.    *          is less than <size>, the values of the remaining elements are
  657.    *          not guaranteed.
  658.    *
  659.    *  Notes:  Please keep in mind that the pointers returned indicate strings
  660.    *          stored in static memory.  Don't free() them, don't write over
  661.    *          them, etc.  Just read them.
  662.    * ------------------------------------------------------------------------ **
  663.    */
  664.  
  665. /* -------------------------------------------------------------------------- **
  666.  * Masquarade...
  667.  *
  668.  * This set of defines allows you to write programs that will use any of the
  669.  * implemented binary tree modules (currently BinTree, AVLtree, and SplayTree).
  670.  * Instead of using ubi_bt..., use ubi_tr..., and select the tree type by
  671.  * including the appropriate module header.
  672.  */
  673.  
  674. #define ubi_trItemPtr ubi_btItemPtr
  675.  
  676. #define ubi_trNode    ubi_btNode
  677. #define ubi_trNodePtr ubi_btNodePtr
  678.  
  679. #define ubi_trRoot    ubi_btRoot
  680. #define ubi_trRootPtr ubi_btRootPtr
  681.  
  682. #define ubi_trCompFunc    ubi_btCompFunc
  683. #define ubi_trActionRtn   ubi_btActionRtn
  684. #define ubi_trKillNodeRtn ubi_btKillNodeRtn
  685.  
  686. #define ubi_trSgn( x ) ubi_btSgn( x )
  687.  
  688. #define ubi_trInitNode( Np ) ubi_btInitNode( (ubi_btNodePtr)(Np) )
  689.  
  690. #define ubi_trInitTree( Rp, Cf, Fl ) \
  691.         ubi_btInitTree( (ubi_btRootPtr)(Rp), (ubi_btCompFunc)(Cf), (Fl) )
  692.  
  693. #define ubi_trInsert( Rp, Nn, Ip, On ) \
  694.         ubi_btInsert( (ubi_btRootPtr)(Rp), (ubi_btNodePtr)(Nn), \
  695.                       (ubi_btItemPtr)(Ip), (ubi_btNodePtr *)(On) )
  696.  
  697. #define ubi_trRemove( Rp, Dn ) \
  698.         ubi_btRemove( (ubi_btRootPtr)(Rp), (ubi_btNodePtr)(Dn) )
  699.  
  700. #define ubi_trLocate( Rp, Ip, Op ) \
  701.         ubi_btLocate( (ubi_btRootPtr)(Rp), \
  702.                       (ubi_btItemPtr)(Ip), \
  703.                       (ubi_trCompOps)(Op) )
  704.  
  705. #define ubi_trFind( Rp, Ip ) \
  706.         ubi_btFind( (ubi_btRootPtr)(Rp), (ubi_btItemPtr)(Ip) )
  707.  
  708. #define ubi_trNext( P ) ubi_btNext( (ubi_btNodePtr)(P) )
  709.  
  710. #define ubi_trPrev( P ) ubi_btPrev( (ubi_btNodePtr)(P) )
  711.  
  712. #define ubi_trFirst( P ) ubi_btFirst( (ubi_btNodePtr)(P) )
  713.  
  714. #define ubi_trLast( P ) ubi_btLast( (ubi_btNodePtr)(P) )
  715.  
  716. #define ubi_trFirstOf( Rp, Ip, P ) \
  717.         ubi_btFirstOf( (ubi_btRootPtr)(Rp), \
  718.                        (ubi_btItemPtr)(Ip), \
  719.                        (ubi_btNodePtr)(P) )
  720.  
  721. #define ubi_trLastOf( Rp, Ip, P ) \
  722.         ubi_btLastOf( (ubi_btRootPtr)(Rp), \
  723.                       (ubi_btItemPtr)(Ip), \
  724.                       (ubi_btNodePtr)(P) )
  725.  
  726. #define ubi_trTraverse( Rp, En, Ud ) \
  727.         ubi_btTraverse((ubi_btRootPtr)(Rp), (ubi_btActionRtn)(En), (void *)(Ud))
  728.  
  729. #define ubi_trKillTree( Rp, Fn ) \
  730.         ubi_btKillTree( (ubi_btRootPtr)(Rp), (ubi_btKillNodeRtn)(Fn) )
  731.  
  732. #define ubi_trLeafNode( Nd ) \
  733.         ubi_btLeafNode( (ubi_btNodePtr)(Nd) )
  734.  
  735. #define ubi_trModuleID( s, l ) ubi_btModuleID( s, l )
  736.  
  737. /* ========================================================================== */
  738. #endif /* ubi_BinTree_H */
  739.